





<!DOCTYPE html>
<html class="writer-html5" lang="zh-CN" >
<head>
  <meta charset="utf-8">
  
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  
  <title>Algebraic Data Types in Relay &mdash; tvm 0.8.dev1982 文档</title>
  

  
  <link rel="stylesheet" href="https://maxcdn.bootstrapcdn.com/bootstrap/4.0.0/css/bootstrap.min.css" integrity="sha384-Gn5384xqQ1aoWXA+058RXPxPg6fy4IWvTNh0E263XmFcJlSAwiGgFAW/dAiS6JXm" crossorigin="anonymous">
  <link rel="stylesheet" href="../../_static/css/theme.css" type="text/css" />
  <link rel="stylesheet" href="../../_static/pygments.css" type="text/css" />
  <link rel="stylesheet" href="../../_static/css/theme.css" type="text/css" />
  <link rel="stylesheet" href="../../_static/gallery.css" type="text/css" />
  <link rel="stylesheet" href="../../_static/pygments.css" type="text/css" />
  <link rel="stylesheet" href="../../_static/css/tlcpack_theme.css" type="text/css" />

  
  
    <link rel="shortcut icon" href="../../_static/tvm-logo-square.png"/>
  

  
  
  
  
    
      <script type="text/javascript" id="documentation_options" data-url_root="../../" src="../../_static/documentation_options.js"></script>
        <script data-url_root="../../" id="documentation_options" src="../../_static/documentation_options.js"></script>
        <script src="../../_static/jquery.js"></script>
        <script src="../../_static/underscore.js"></script>
        <script src="../../_static/doctools.js"></script>
        <script src="../../_static/translations.js"></script>
    
    <script type="text/javascript" src="../../_static/js/theme.js"></script>

    
    <script type="text/javascript" src="../../_static/js/tlcpack_theme.js"></script>
    <link rel="index" title="索引" href="../../genindex.html" />
    <link rel="search" title="搜索" href="../../search.html" />
    <link rel="next" title="Relay 基础张量算子" href="relay_op.html" />
    <link rel="prev" title="Relay 系统类型" href="relay_type.html" /> 
</head>

<body class="wy-body-for-nav">

   
  <div class="wy-grid-for-nav">
    
    
<header class="header">
    <div class="innercontainer">
      <div class="headerInner d-flex justify-content-between align-items-center">
          <div class="headerLogo">
               <a href="https://tvm.apache.org/"><img src=https://tvm.apache.org/assets/images/logo.svg alt="logo"></a>
          </div>

          <div id="headMenu" class="headerNav">
            <button type="button" id="closeHeadMenu" class="navCloseBtn"><img src="../../_static/img/close-icon.svg" alt="Close"></button>
             <ul class="nav">
                <li class="nav-item">
                   <a class="nav-link" href=https://tvm.apache.org/community>Community</a>
                </li>
                <li class="nav-item">
                   <a class="nav-link" href=https://tvm.apache.org/download>Download</a>
                </li>
                <li class="nav-item">
                   <a class="nav-link" href=https://tvm.apache.org/vta>VTA</a>
                </li>
                <li class="nav-item">
                   <a class="nav-link" href=https://tvm.apache.org/blog>Blog</a>
                </li>
                <li class="nav-item">
                   <a class="nav-link" href=https://tvm.apache.org/docs>Docs</a>
                </li>
                <li class="nav-item">
                   <a class="nav-link" href=https://tvmconf.org>Conference</a>
                </li>
                <li class="nav-item">
                   <a class="nav-link" href=https://github.com/apache/tvm/>Github</a>
                </li>
                <li class="nav-item">
                   <a class="nav-link" href=https://tvmchinese.github.io/declaration_zh_CN.html>About-Translators</a>
                </li>
             </ul>
               <div class="responsivetlcdropdown">
                 <button type="button" class="btn-link">
                   ASF
                 </button>
                 <ul>
                     <li>
                       <a href=https://apache.org/>Apache Homepage</a>
                     </li>
                     <li>
                       <a href=https://www.apache.org/licenses/>License</a>
                     </li>
                     <li>
                       <a href=https://www.apache.org/foundation/sponsorship.html>Sponsorship</a>
                     </li>
                     <li>
                       <a href=https://www.apache.org/security/>Security</a>
                     </li>
                     <li>
                       <a href=https://www.apache.org/foundation/thanks.html>Thanks</a>
                     </li>
                     <li>
                       <a href=https://www.apache.org/events/current-event>Events</a>
                     </li>
                     <li>
                       <a href=https://www.zhihu.com/column/c_1429578595417563136>Zhihu</a>
                     </li>
                 </ul>
               </div>
          </div>
            <div class="responsiveMenuIcon">
              <button type="button" id="menuBtn" class="btn-menu"><img src="../../_static/img/menu-icon.svg" alt="Menu Icon"></button>
            </div>

            <div class="tlcDropdown">
              <div class="dropdown">
                <button type="button" class="btn-link dropdown-toggle" data-toggle="dropdown" aria-haspopup="true" aria-expanded="false">
                  ASF
                </button>
                <div class="dropdown-menu dropdown-menu-right">
                  <ul>
                     <li>
                       <a href=https://apache.org/>Apache Homepage</a>
                     </li>
                     <li>
                       <a href=https://www.apache.org/licenses/>License</a>
                     </li>
                     <li>
                       <a href=https://www.apache.org/foundation/sponsorship.html>Sponsorship</a>
                     </li>
                     <li>
                       <a href=https://www.apache.org/security/>Security</a>
                     </li>
                     <li>
                       <a href=https://www.apache.org/foundation/thanks.html>Thanks</a>
                     </li>
                     <li>
                       <a href=https://www.apache.org/events/current-event>Events</a>
                     </li>
                     <li>
                       <a href=https://www.zhihu.com/column/c_1429578595417563136>Zhihu</a>
                     </li>
                  </ul>
                </div>
              </div>
          </div>
       </div>
    </div>
 </header>
 
    <nav data-toggle="wy-nav-shift" class="wy-nav-side fixed">
      <div class="wy-side-scroll">
        <div class="wy-side-nav-search" >
          

          
            <a href="../../index.html">
          

          
            
            <img src="../../_static/tvm-logo-small.png" class="logo" alt="Logo"/>
          
          </a>

          
            
            
                <div class="version">
                  0.8.dev1982
                </div>
            
          

          
<div role="search">
  <form id="rtd-search-form" class="wy-form" action="../../search.html" method="get">
    <input type="text" name="q" placeholder="Search docs" />
    <input type="hidden" name="check_keywords" value="yes" />
    <input type="hidden" name="area" value="default" />
  </form>
</div>

          
        </div>

        
        <div class="wy-menu wy-menu-vertical" data-spy="affix" role="navigation" aria-label="main navigation">
          
            
            
              
            
            
              <p class="caption" role="heading"><span class="caption-text">如何开始</span></p>
<ul>
<li class="toctree-l1"><a class="reference internal" href="../../install/index.html">安装 TVM</a></li>
<li class="toctree-l1"><a class="reference internal" href="../../contribute/index.html">贡献者指南</a></li>
</ul>
<p class="caption" role="heading"><span class="caption-text">用户引导</span></p>
<ul>
<li class="toctree-l1"><a class="reference internal" href="../../tutorial/index.html">User Tutorial</a></li>
<li class="toctree-l1"><a class="reference internal" href="../../how_to/index.html">How To Guides</a></li>
</ul>
<p class="caption" role="heading"><span class="caption-text">开发者引导</span></p>
<ul>
<li class="toctree-l1"><a class="reference internal" href="../../dev/tutorial/index.html">Developer Tutorial</a></li>
<li class="toctree-l1"><a class="reference internal" href="../../dev/how_to/how_to.html">开发者指南</a></li>
</ul>
<p class="caption" role="heading"><span class="caption-text">架构指南</span></p>
<ul>
<li class="toctree-l1"><a class="reference internal" href="../../arch/index.html">Design and Architecture</a></li>
</ul>
<p class="caption" role="heading"><span class="caption-text">主题引导</span></p>
<ul>
<li class="toctree-l1"><a class="reference internal" href="../../topic/microtvm/index.html">microTVM：裸机使用TVM</a></li>
<li class="toctree-l1"><a class="reference internal" href="../../topic/vta/index.html">VTA: Versatile Tensor Accelerator</a></li>
</ul>
<p class="caption" role="heading"><span class="caption-text">参考指南</span></p>
<ul class="current">
<li class="toctree-l1 current"><a class="reference internal" href="index.html">语言参考</a><ul class="current">
<li class="toctree-l2 current"><a class="reference internal" href="index.html#introduction-to-relay">Relay简介</a><ul class="current">
<li class="toctree-l3"><a class="reference internal" href="relay_expr.html">Expressions in Relay</a></li>
<li class="toctree-l3"><a class="reference internal" href="relay_type.html">Relay 系统类型</a></li>
<li class="toctree-l3 current"><a class="current reference internal" href="#">Algebraic Data Types in Relay</a><ul>
<li class="toctree-l4"><a class="reference internal" href="#defining-and-matching-on-an-adt">Defining and Matching on an ADT</a></li>
<li class="toctree-l4"><a class="reference internal" href="#type-checking-adts-and-polymorphism">Type-Checking ADTs and Polymorphism</a></li>
<li class="toctree-l4"><a class="reference internal" href="#recursion-with-adts">Recursion with ADTs</a></li>
<li class="toctree-l4"><a class="reference internal" href="#pattern-matching-in-match-expressions">Pattern Matching in Match Expressions</a></li>
<li class="toctree-l4"><a class="reference internal" href="#common-adt-uses">Common ADT Uses</a></li>
<li class="toctree-l4"><a class="reference internal" href="#implementing-neural-nets-using-adts">Implementing Neural Nets Using ADTs</a></li>
</ul>
</li>
<li class="toctree-l3"><a class="reference internal" href="relay_op.html">Relay 基础张量算子</a></li>
<li class="toctree-l3"><a class="reference internal" href="relay_pattern.html">Pattern Matching in Relay</a></li>
</ul>
</li>
<li class="toctree-l2"><a class="reference internal" href="index.html#hybrid-script">混合式脚本</a></li>
</ul>
</li>
<li class="toctree-l1"><a class="reference internal" href="../api/python/index.html">Python API</a></li>
<li class="toctree-l1"><a class="reference internal" href="../api/links.html">Other APIs</a></li>
<li class="toctree-l1"><a class="reference internal" href="../publications.html">Publications</a></li>
<li class="toctree-l1"><a class="reference internal" href="../../genindex.html">索引</a></li>
</ul>

            
          
        </div>
        
      </div>
    </nav>

    <section data-toggle="wy-nav-shift" class="wy-nav-content-wrap">
      
      <nav class="wy-nav-top" aria-label="top navigation" data-toggle="wy-nav-top">
        
            <div class="togglemenu">

            </div>
            <div class="nav-content">
              <!-- tvm -->
              Table of content
            </div>
        
      </nav>


      <div class="wy-nav-content">
        
        <div class="rst-content">
        

          




















<div role="navigation" aria-label="breadcrumbs navigation">

  <ul class="wy-breadcrumbs">
    
      <li><a href="../../index.html">Docs</a> <span class="br-arrow">></span></li>
        
          <li><a href="index.html">语言参考</a> <span class="br-arrow">></span></li>
        
      <li>Algebraic Data Types in Relay</li>
    
    
      <li class="wy-breadcrumbs-aside">
        
            
            <a href="../../_sources/reference/langref/relay_adt.rst.txt" rel="nofollow"> <img src="../../_static//img/source.svg" alt="viewsource"/></a>
          
        
      </li>
    
  </ul>

  
  <hr/>
</div>
          <div role="main" class="document" itemscope="itemscope" itemtype="http://schema.org/Article">
           <div itemprop="articleBody">
            
  <div class="section" id="algebraic-data-types-in-relay">
<span id="adt-overview"></span><h1>Algebraic Data Types in Relay<a class="headerlink" href="#algebraic-data-types-in-relay" title="永久链接至标题">¶</a></h1>
<p>Algebraic data types (ADTs) are a staple feature of functional programming languages,
particularly those derived from ML, because they express data structures in a
manner that is easy to reason about when writing recursive computations.
Because recursion is intended to be one of the primary mechanisms of control
flow in Relay, it is important that Relay include ADTs in order to best express
loops and other control flow structures that must be implemented using recursion.</p>
<div class="section" id="defining-and-matching-on-an-adt">
<h2>Defining and Matching on an ADT<a class="headerlink" href="#defining-and-matching-on-an-adt" title="永久链接至标题">¶</a></h2>
<p><em>Note: ADTs are not presently supported in the text format. The syntax here is speculative, based on ADTs in other languages.</em></p>
<p>ADTs can be understood as a generalized version of <code class="code docutils literal notranslate"><span class="pre">enum</span></code> and <code class="code docutils literal notranslate"><span class="pre">struct</span></code> types
from C-like languages. Like a C <code class="code docutils literal notranslate"><span class="pre">struct:</span></code>, an ADT instance is a container for fields
of specified types, but the type system allows for the same type to encode different possible
groupings of fields in a systematic manner, similar to C <code class="code docutils literal notranslate"><span class="pre">enum</span></code> types, which are
defined using a finite set of possible values named by the user.</p>
<p>Specifically, an ADT is defined as a named group of constructors, each of which is
a function that takes values of specified types as arguments and returns an instance
of the named ADT. An ADT instance simply contains the values of the arguments
passed to the constructor call used to produce it.</p>
<p>An ADT value is opaque until it is <em>deconstructed</em>, allowing the arguments to the
constructor to be accessed again and used to compute new values. Because
a particular ADT can have multiple constructors with different signatures,
it is usually necessary to branch on the different possible constructors,
resulting in the <em>match</em> syntax for ADTs. Hence, ADTs are sometimes called
“tagged unions” because an ADT instance is tagged by the name of the constructor
used to produce it and can later be inspected based on the tag.</p>
<p>Because each ADT has a finite set of constructors, it is straightforward to determine
whether a function processing an ADT instance is handling all possible cases.
In particular, the type system can ensure that types are properly assigned in all cases when
deconstructing an ADT instance, in contrast to <code class="code docutils literal notranslate"><span class="pre">union</span></code> types in C.
Hence, it is often easy to reason about ADTs.</p>
<p><em>Implementation detail: Relay ADT definitions are global and are stored in the module, similarly to global function definitions. An ADT name is, in fact, a global type variable (just as a global function name is a global variable). The module keeps a mapping of ADT names (global type variables) to the list of constructors for that ADT.</em></p>
<p>Below is a simple example of defining an ADT and using it in a function
via a match expression:</p>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span># Defines an ADT named &quot;Numbers&quot;
data Numbers {
  Empty : () -&gt; Numbers
  Single : (Tensor[(), int32]) -&gt; Numbers
  Pair : (Tensor[(), int32], Tensor[(), int32]) -&gt; Numbers
}
# A Numbers value can be produced using an Empty, Single, or Pair
# constructor, each with a signature given above

def @sum(%n : Numbers[]) -&gt; Tensor[(), int32] {
   # The match expression branches on the constructor that was
   # used to produce %n. The variables in each case are bound
   # if the constructor matches that used for %n
   match(%n) {
     case Empty() { 0 }
     case Single(x) { x }
     case Pair(x, y) { x + y }
   }
}

@sum(Empty())    # evaluates to 0
@sum(Single(3))  # evaluates to 3
@sum(Pair(5, 6)) # evaluates to 11
</pre></div>
</div>
<p>Note that ADTs are identified by name,
meaning that two ADTs with structurally identical constructors
will nevertheless be distinct data types from the point of view of
the typechecker.</p>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="c1"># structurally identical constructors to Numbers</span>
<span class="n">data</span> <span class="n">Numbers2</span> <span class="p">{</span>
  <span class="n">Empty2</span> <span class="p">:</span> <span class="p">()</span> <span class="o">-&gt;</span> <span class="n">Numbers2</span>
  <span class="n">Single2</span> <span class="p">:</span> <span class="p">(</span><span class="n">Tensor</span><span class="p">[(),</span> <span class="n">int32</span><span class="p">])</span> <span class="o">-&gt;</span> <span class="n">Numbers2</span>
  <span class="n">Pair2</span> <span class="p">:</span> <span class="p">(</span><span class="n">Tensor</span><span class="p">[(),</span> <span class="n">int32</span><span class="p">],</span> <span class="n">Tensor</span><span class="p">[(),</span> <span class="n">int32</span><span class="p">])</span> <span class="o">-&gt;</span> <span class="n">Numbers2</span>
<span class="p">}</span>

<span class="c1"># the below results in a type error because Numbers2</span>
<span class="c1"># is a distinct type from Numbers</span>
<span class="c1"># fn() { @sum(Empty2()) }</span>
</pre></div>
</div>
</div>
<div class="section" id="type-checking-adts-and-polymorphism">
<h2>Type-Checking ADTs and Polymorphism<a class="headerlink" href="#type-checking-adts-and-polymorphism" title="永久链接至标题">¶</a></h2>
<p>This section will go into more specific detail about the typing of ADTs.
Most of the complexity involved results from the fact that, as with functions, ADTs
can be polymorphic and take type parameters.</p>
<p>For example, one of the standard ADTs commonly used in functional
programming languages is the optional type, defined here:</p>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="c1"># a is a type parameter</span>
<span class="n">data</span> <span class="n">Optional</span><span class="o">&lt;</span><span class="n">a</span><span class="o">&gt;</span> <span class="p">{</span>
  <span class="kc">None</span> <span class="p">:</span> <span class="p">()</span> <span class="o">-&gt;</span> <span class="n">Optional</span>
  <span class="n">Some</span> <span class="p">:</span> <span class="p">(</span><span class="n">a</span><span class="p">)</span> <span class="o">-&gt;</span> <span class="n">Optional</span>
<span class="p">}</span>
</pre></div>
</div>
<p>Optional types are commonly used as the return type for any operation
involving querying into a data structure (returning <code class="code docutils literal notranslate"><span class="pre">Some(v)</span></code>
if a value is found and <code class="code docutils literal notranslate"><span class="pre">None</span></code> if it isn’t).
Taking a type parameter in the definition allows the same optional type
to be used in a wide variety of situations, rather than having to
define a unique ADT for each different type that could be contained in it.</p>
<p>However, it is important to ensure that option types whose contents
are of different types can still be distinguished by the type system,
since it would violate type safety if a function expecting an option
containing a <code class="code docutils literal notranslate"><span class="pre">Tensor[(),</span> <span class="pre">int32]</span></code> instead receives an option
containing a <code class="code docutils literal notranslate"><span class="pre">Tensor[(3,</span> <span class="pre">4),</span> <span class="pre">float32]</span></code>. As this example may
imply, an ADT instance is thus given a type that contains the
concrete type arguments for that instance, ensuring the information is
kept around. Let the below example illustrate:</p>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span># the signature for option indicates the type argument
def @inc_scalar(%opt : Optional[Tensor[(), int32]]) -&gt; Tensor[(), int32] {
  match(%opt) {
    case None() { 1 }
    case Some(%s) { %s + 1 }
  }
}

def @main() {
  let %one : Optional[Tensor[(), int32]] = Some(1);
  let %big : Optional[Tensor[(10, 10), float32]]
    = Some(Constant(1, (10, 10), float32));
  let %two = inc_scalar(%one);
  # let %bigger = inc_scalar(%big); # type system rejects
  # None does not take an argument so it can always implicitly
  # be given the correct type arguments
  let %z = inc_scalar(None());
  ()
}
</pre></div>
</div>
<p>The syntax for the annotated type arguments
(e.g., <code class="code docutils literal notranslate"><span class="pre">Optional[Tensor[(),</span> <span class="pre">int32]]</span></code>) in the above examples is
called a “type call,” treating the polymorphic ADT definition as a
type-level function (taking type params and returning a type, namely
the ADT). Any ADT appearing in a type annotation or function signature
must be annotated with type arguments (a non-polymorphic ADT must be
in a type call with no arguments).</p>
<p>Thus, we can say in general that if constructor <code class="code docutils literal notranslate"><span class="pre">C</span></code> that
takes arguments of types <code class="code docutils literal notranslate"><span class="pre">T1,</span> <span class="pre">...,</span> <span class="pre">Tn</span></code> is a constructor
for an ADT <code class="code docutils literal notranslate"><span class="pre">D</span></code> that takes type parameters <code class="code docutils literal notranslate"><span class="pre">v1,</span> <span class="pre">...,</span> <span class="pre">vn</span></code>
(where <code class="code docutils literal notranslate"><span class="pre">T1,</span> <span class="pre">...,</span> <span class="pre">Tn</span></code> may contain any of the <code class="code docutils literal notranslate"><span class="pre">v1,</span> <span class="pre">...,</span> <span class="pre">vn</span></code>),
then <code class="code docutils literal notranslate"><span class="pre">C</span></code> has
the type <code class="code docutils literal notranslate"><span class="pre">fun&lt;v1,</span> <span class="pre">...,</span> <span class="pre">vn&gt;(T1,</span> <span class="pre">...,</span> <span class="pre">Tn)</span> <span class="pre">-&gt;</span> <span class="pre">D[v1,</span> <span class="pre">...,</span> <span class="pre">vn]</span></code>.
This means that constructors are typed like ordinary functions and
thus appear inside call nodes and can be passed to or returned by
other functions. In particular, the <code class="code docutils literal notranslate"><span class="pre">Some</span></code> example above has
the signature <code class="code docutils literal notranslate"><span class="pre">fun&lt;a&gt;(a)</span> <span class="pre">-&gt;</span> <span class="pre">Optional[a]</span></code>, while <code class="code docutils literal notranslate"><span class="pre">None</span></code>
has the signature <code class="code docutils literal notranslate"><span class="pre">fun&lt;a&gt;()</span> <span class="pre">-&gt;</span> <span class="pre">Optional[a]</span></code>.</p>
</div>
<div class="section" id="recursion-with-adts">
<h2>Recursion with ADTs<a class="headerlink" href="#recursion-with-adts" title="永久链接至标题">¶</a></h2>
<p>ADT definitions are allowed to be recursive, that is, a definition for
an ADT named <code class="code docutils literal notranslate"><span class="pre">D</span></code> can assume the existence of type <code class="code docutils literal notranslate"><span class="pre">D</span></code> and
use it as an argument to constructors. Recursion allows ADTs to
represent complex structures such as lists or trees; it is the source
of much of ADTs’ power in functional programming, since an appropriately
designed data structure could make it easy to concisely express a
computation with a recursive function.</p>
<p>Many commonly used ADTs involve recursion; some of these are given
in <a class="reference internal" href="#common-adt-uses">Common ADT Uses</a>. As an example here, we will
examine the list ADT, ubiquitous in functional languages:</p>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">data</span> <span class="n">List</span><span class="o">&lt;</span><span class="n">a</span><span class="o">&gt;</span> <span class="p">{</span>
   <span class="n">Nil</span> <span class="p">:</span> <span class="p">()</span> <span class="o">-&gt;</span> <span class="n">List</span>
   <span class="n">Cons</span> <span class="p">:</span> <span class="p">(</span><span class="n">a</span><span class="p">,</span> <span class="n">List</span><span class="p">[</span><span class="n">a</span><span class="p">])</span> <span class="o">-&gt;</span> <span class="n">List</span>
<span class="p">}</span>
</pre></div>
</div>
<p>(Notice that the recursive reference to <code class="code docutils literal notranslate"><span class="pre">List</span></code> is wrapped
in a type call even in the constructor.)</p>
<p>The above definition means that a list of values of a particular type
can be represented by nesting <code class="code docutils literal notranslate"><span class="pre">Cons</span></code> constructors until the
end of the list is reached, which can be indicated with a <code class="code docutils literal notranslate"><span class="pre">Nil</span></code>
(representing an empty list).</p>
<p>Lists represented in this manner can easily be recursively processed.
For example, the following function sums a list of integers:</p>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span>def @list_sum(%l : List[Tensor[(), int32]]) -&gt; Tensor[(), int32] {
  match(%l) {
    case Nil() { 0 }
    # add the head of the list to the sum of the tail
    case Cons(%h, %t) { %h + @list_sum(%t) }
  }
}
</pre></div>
</div>
<p>As it happens, many recursive functions on lists like the one just given
share structures that can be factored out into generic, easily
usable functions that will be discussed under <a class="reference internal" href="#common-adt-uses">Common ADT Uses</a>.</p>
</div>
<div class="section" id="pattern-matching-in-match-expressions">
<span id="adt-pattern"></span><h2>Pattern Matching in Match Expressions<a class="headerlink" href="#pattern-matching-in-match-expressions" title="永久链接至标题">¶</a></h2>
<p>Match expressions in Relay, as in other functional languages, are capable of
more versatile pattern matching than simply having one case for each constructor
for the datatype of the value being deconstructed.</p>
<p>In particular, the patterns in match cases can be built up recursively:</p>
<ul class="simple">
<li><p>Constructor patterns match for a particular ADT constructor. If a value matches the constructor, each argument to the constructor will be matched against a nested pattern.</p></li>
<li><p>Wildcard patterns will match any value and will not bind to a variable.</p></li>
<li><p>Variable patterns will match any value and bind it to a local variable, scoped to the match clause.</p></li>
</ul>
<p>In the simple case of <code class="code docutils literal notranslate"><span class="pre">&#64;list_sum</span></code> above, the first match case has a <code class="code docutils literal notranslate"><span class="pre">Nil</span></code> constructor pattern (with no nested arguments)
and the second has a <code class="code docutils literal notranslate"><span class="pre">Cons</span></code> constructor pattern that uses variable patterns for each of the arguments to <code class="code docutils literal notranslate"><span class="pre">Cons</span></code>.</p>
<p>The below example uses a wildcard pattern to ignore one of the arguments to <code class="code docutils literal notranslate"><span class="pre">Cons</span></code>:</p>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span>def @first&lt;a&gt;(%l : List[a]) -&gt; Optional[a] {
  match(%l) {
    case Nil() { None() }
    case Cons(%h, _) { Some(%h) } # list tail is unused and ignored
  }
}
</pre></div>
</div>
<p>Here, a constructor pattern is nested inside another constructor pattern to avoid nested match expressions for a list option.
A top-level wildcard pattern is also used to handle all cases that do not match the first clause:</p>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span>def @second_opt&lt;a&gt;(%ll : Optional[List[a]]) -&gt; Optional[a] {
  match(%ll) {
    # we only need the second member of the list if there is one
    case Some(Cons(_, Cons(%s, _))) { Some(%s) }
    case _ { None() }
  }
}

# @second_opt(Some(Cons(1, Nil()))) evaluates to None()
# @second_opt(Some(Cons(1, Cons(2, Nil())))) evaluates to Some(2)
# @second_opt(Some(Nil())) evaluates to None()
# @second_opt(None()) evaluates to None()
</pre></div>
</div>
<p>Note that a match expression checks its patterns in the order the cases are listed: the first clause whose pattern
that matches the input value is the one that is evaluated. Here, a top-level variable pattern binds the whole
input value:</p>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span>def @match_order_beware&lt;a&gt;(%l : List[a]) -&gt; List[a] {
  match(%l) {
    case %v { %v }
    # the above matches everything so neither of these runs
    case Cons(%h, %t) { Cons(%h, @match_order_beware(%t)) }
    case Nil() { Nil() }
  }
}
</pre></div>
</div>
</div>
<div class="section" id="common-adt-uses">
<h2>Common ADT Uses<a class="headerlink" href="#common-adt-uses" title="永久链接至标题">¶</a></h2>
<p>In functional programming languages, certain ADTs provide useful facilities for writing common programs.
Parametric polymorphism and higher-order functions allow these ADTs to be easily reuseable and for generic
functions to manipulate them in common situations. Relay includes a “Prelude” of certain pre-defined ADTs
and functions for them that correspond to the indispensable ADTs of other languages.</p>
<p>The option type defined under <a class="reference internal" href="#type-checking-adts-and-polymorphism">Type-Checking ADTs and Polymorphism</a> is one such ADT, used
whenever it can make sense for a function to only return a value under certain circumstances. Having
the option type allows for the type system to keep track of which functions always return a value
of a certain type versus returning an option of that type, ensuring that any options are always
explicitly checked (contrast with returning null pointers or throwing
exceptions as other ways to addressing that problem).</p>
<p>Lists (defined in <a class="reference internal" href="#recursion-with-adts">Recursion with ADTs</a>) can be manipulated by generic functions in a manner similar to
list comprehensions and certain library functions in Python. Below are very common functions for iterating
through lists, which are included in Relay’s Prelude. (These have all been extensively characterized
in the functional programming literature, and we do not attempt to reproduce that work in this document.)</p>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span># Map: for [h1, h2, ..., hn] returns [f(h1), f(h2), ..., f(hn)]
def @map&lt;a, b&gt;(%f : fn(a) -&gt; b, %l : List[a]) -&gt; List[b] {
  match(%l) {
    case Nil() { Nil() }
    case Cons(%h, %t) { Cons(%f(%h), @map(%f, %t)) }
  }
}

# Left fold: for [h1, h2, ..., hn] returns f(...(f(f(z, h1), h2)...), hn)
def @foldl&lt;a, b&gt;(%f : fn(b, a) -&gt; b, %z : b, %l : List[a]) -&gt; b {
  match(%l) {
    case Nil() { %z }
    case Cons(%h, %t) { @foldl(%f, %f(%z, %h), %t) }
  }
}

# Right fold: for [h1, h2, ..., hn] returns f(h1, f(h2, f(..., (f(hn, z)...)
def @foldr&lt;a, b&gt;(%f : fn(a, b) -&gt; b, %z : b, %l : List[a] -&gt; b {
  match(%l) {
    case Nil() { %z }
    case Cons(%h, %t) { %f(%h, @foldr(%f, %z, %t)) }
  }
}
</pre></div>
</div>
<p>Using these iteration constructs, many common operations over lists can be expressed compactly.
For example, the following map doubles all members of a list:</p>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span># directly written
def @double(%l : List[Tensor[(), int32]]) -&gt; List[Tensor[(), int32]] {
  match(%l) {
    case Nil() { Nil() }
    case Cons(%h, %t) { Cons(%h * 2, @double(%t)) }
  }
}

# map takes care of the recursion
@map(fn(%i) { %i * 2 }, %l)
</pre></div>
</div>
<p>The following right fold concatenates two lists:</p>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span># directly written
def @concat&lt;a&gt;(%l1 : List[a], %l2 : List[a]) -&gt; List[a] {
  match(%l1) {
    case Nil() { %l2 }
    case Cons(%h, %t) { Cons(%h, @concat(%t, %l2) }
  }
}

# foldr takes care of the recursion
@foldr(fn(%h, %z) { Cons(%h, %z) }, %l2, %l1)
</pre></div>
</div>
<p>The following left fold flattens a list of lists (using concatenation):</p>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span># directly written
def @flatten&lt;a&gt;(%ll : List[List[a]]) -&gt; List[a] {
  match(%ll) {
    case Cons(%h, %t) { @concat(%h, @flatten(%t)) }
    case Nil() { Nil() }
  }

# foldl takes care of the recursion
@foldl(@concat, Nil(), %ll)
</pre></div>
</div>
<p>Note that these iteration constructs can be implemented directly in Relay’s
source language and more can easily be defined (and for more data types, like trees),
rather than being constructs built into the language (e.g.,
<a class="reference external" href="https://mxnet.apache.org/versions/master/tutorials/control_flow/ControlFlowTutorial.html">“foreach” in MXNet</a>).
ADTs and their extensibility allow for a broad range of iterations and data structures to be expressed
in Relay and supported by the type system without having to modify the language implementation.</p>
</div>
<div class="section" id="implementing-neural-nets-using-adts">
<h2>Implementing Neural Nets Using ADTs<a class="headerlink" href="#implementing-neural-nets-using-adts" title="永久链接至标题">¶</a></h2>
<p>In <a class="reference external" href="http://colah.github.io/posts/2015-09-NN-Types-FP/">this 2015 blog post</a>, Christopher Olah notes that
many neural networks can be easily expressed using common functional programming constructs. Relay’s ADTs
allow those examples to be implemented directly in TVM.</p>
<p>First let us suppose that we have a function corresponding to a trained recurrent neural net (RNN)
cell, which takes in a past state and an input value and returns a new state and output value. In
Relay, this would have the following signature:</p>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="nd">@cell</span> <span class="p">:</span> <span class="n">fn</span><span class="o">&lt;</span><span class="n">state_type</span><span class="p">,</span> <span class="n">in_type</span><span class="p">,</span> <span class="n">out_type</span><span class="o">&gt;</span><span class="p">(</span><span class="n">state_type</span><span class="p">,</span> <span class="n">in_type</span><span class="p">)</span> <span class="o">-&gt;</span> <span class="p">(</span><span class="n">state_type</span><span class="p">,</span> <span class="n">out_type</span><span class="p">)</span>
</pre></div>
</div>
<p>We might consider a ReLU cell as a simple concrete example, with a trained version below:</p>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span>def @linear(%x, %w, %b) { %w*%x + %b }

def @relu_cell(%w, # weights
               %b, # offsets
               %s, # state
               %x  # input
) {
  let %x2 = @linear(%x, %w.0, %b.0);
  let %s2 = @linear(%s, %w.1, %b.1);
  # doesn&#39;t change the state
  (%s, nn.relu(%x2 + %s2))
}

# this is a higher-order function because it returns a closure
def @trained_cell(%w, %b) {
  fn(%x, %h) { @relu_cell(%w, %b, %x, %h) }
}
</pre></div>
</div>
<p>Following Olah’s example, we can encode a sequence (list) of inputs with the following left fold:</p>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span>def @encode&lt;state_type, in_type, out_type&gt;(%cell, %input : List[in_type], %init : state_type) -&gt; state_type {
  # not using the output
  @foldl(fn(%state, %in) { %cell(%state, %in).0 }, %init, %input)
}
</pre></div>
</div>
<p>Using an <em>unfold</em> iterator (from Haskell’s standard library), the same cell could be used to make
a generator network (which takes a single input and produces a sequence of outputs):</p>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span># included in Relay&#39;s Prelude
def @unfoldr&lt;a, b&gt;(%f : fn(b) -&gt; Optional[(a, b)], %z : b) -&gt; List[a] {
  match(%f(%z)) {
    case Some(%pair) { Cons(%pair.0, @unfoldr(%f, %pair.1)) }
    case None() { Nil() }
  }
}

# we need some way of generating an input to the cell function given only a state
def @gen_func&lt;state_type, in_type, out_type&gt;(%state : state_type) : Optional[(out_type, state_type)] {
  let %in : Optional[in_type] = @generate_input(%state);
  match(%in) {
    case Some(%n) {
      let %cell_out = @cell(%n, %state);
      Some((%cell_out.1, %cell_out.0)) # pair of output and state
    }
    case None() { None() }
  }
}

def @generator&lt;state_type, in_type, out_type&gt;(%cell, %init : state_type) -&gt; List[out_type] {
  @unfoldr(fn(%state) { @gen_func(%cell, %state) }, %init)
}
</pre></div>
</div>
<p>An accumulating map (a fold that simultaneously updates an accumulator value and a list
of outputs) can be used to write a general RNN (with an output for every input):</p>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span>def @map_accumr&lt;a, b, c&gt;(%f : fn(a, b) -&gt; (a, c), %acc : a, %l : List[b]) -&gt; (a, List[c]) {
  match(%l) {
    case Nil() { (%acc, Nil()) }
    case Cons(%b, %t) {
      let %update = %f(%acc, %b);
      let %rest = @map_accumr(%f, %update.0, %t));
      (%rest.0, Cons(%update.1, %rest.1))
    }
  }
}

# can also be implemented as a right fold
# (this version is included in Relay&#39;s Prelude)
def @map_accumr_fold(%f, %acc, %l) {
  @foldr(fn(%b, %p) {
    let %f_out = %f(%p.0, %b);
    (%f_out.0, Cons(%f_out.1, %p.1))
  },
  (%acc, Nil()), %l)
}

def @general_rnn&lt;state_type, in_type, out_type&gt;(%cell, %init : state_type, %input : List[in_type])
  -&gt; (state_type, List[out_type]) {
  @map_accumr(%cell, %init, %input)
}
</pre></div>
</div>
<p>Olah also gives an example of a bidirectional neural network, in which two sets of
cells (which may have different weights) process the input in both directions and produce a
single set of outputs. The following is a Relay implementation of that example:</p>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span># creates a list of tuples from two lists
# included in Relay&#39;s Prelude
def @zip&lt;a, b&gt;(%l : List[a], %m : List[b]) -&gt; List[(a, b)] {
  match(%l) {
    case Nil() { Nil() }
    case Cons(%a, %t1) {
      match(%m) {
        case Nil() { Nil() }
        case Cons(%b, %t2) { Cons((%a, %b), @zip(%t1, %t2)) }
      }
    }
  }
}

# analogous to map_accumr
# included in Relay&#39;s Prelude
def @map_accmul(%f, %acc, %l) {
  @foldl(fn(%p, %b){
    let %f_out = %f(%p.0, %b);
    (%f_out.0, Cons(%f_out.1, %p.1))
  }, (%acc, Nil()), %l)
}

def @bidirectional_rnn&lt;state1_type, state2_type, in_type, out1_type, out2_type&gt;
  (%cell1, %cell2, %state1 : state1_type, %state2 : state2_type, %input : List[in_type])
  -&gt; List[(out1_type, out2_type)] {
  @zip(@map_accumr(%cell1, %state1, %input).1, @map_accuml(%cell2, %state2, %input).1)
}
</pre></div>
</div>
</div>
</div>


           </div>
           
          </div>
          

<footer>

    <div class="rst-footer-buttons" role="navigation" aria-label="footer navigation">
      
        <a href="relay_op.html" class="btn btn-neutral float-right" title="Relay 基础张量算子" accesskey="n" rel="next">下一个 <span class="fa fa-arrow-circle-right"></span></a>
      
      
        <a href="relay_type.html" class="btn btn-neutral float-left" title="Relay 系统类型" accesskey="p" rel="prev"><span class="fa fa-arrow-circle-left"></span> 上一个</a>
      
    </div>

<div id="button" class="backtop"><img src="../../_static//img/right.svg" alt="backtop"/> </div>
<section class="footerSec">
    <div class="footerHeader">
      <ul class="d-flex align-md-items-center justify-content-between flex-column flex-md-row">
        <li class="copywrite d-flex align-items-center">
          <h5 id="copy-right-info">© 2020 Apache Software Foundation | All right reserved</h5>
        </li>
      </ul>

    </div>

    <ul>
      <li class="footernote">Copyright © 2020 The Apache Software Foundation. Apache TVM, Apache, the Apache feather, and the Apache TVM project logo are either trademarks or registered trademarks of the Apache Software Foundation.</li>
    </ul>

</section>
</footer>
        </div>
      </div>

    </section>

  </div>
  

    <script src="https://cdnjs.cloudflare.com/ajax/libs/popper.js/1.12.9/umd/popper.min.js" integrity="sha384-ApNbgh9B+Y1QKtv3Rn7W3mgPxhU9K/ScQsAP7hUibX39j7fakFPskvXusvfa0b4Q" crossorigin="anonymous"></script>
    <script src="https://maxcdn.bootstrapcdn.com/bootstrap/4.0.0/js/bootstrap.min.js" integrity="sha384-JZR6Spejh4U02d8jOt6vLEHfe/JQGiRRSQQxSfFWpi1MquVdAyjUar5+76PVCmYl" crossorigin="anonymous"></script>

  </body>
  <script type="text/javascript">
      jQuery(function () {
          SphinxRtdTheme.Navigation.enable(true);
      });
  </script>

  
  
    
    <!-- Theme Analytics -->
    <script>
    (function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){
      (i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),
      m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m)
    })(window,document,'script','https://www.google-analytics.com/analytics.js','ga');

    ga('create', 'UA-75982049-2', 'auto');
    ga('send', 'pageview');
    </script>

    
   

</body>
</html>